<!DOCTYPE html>
<html>
<head>
<link rel="stylesheet" href="../style.css" type="text/css">
<script src="guidance.js"></script>
<title>6.824 Lab 2: Raft</title>
</head>
<body>
<div align="center">
<h2><a href="../index.html">6.824</a> - Spring 2021</h2>
<h1>6.824 Lab 2: Raft</h1>
<h3>Part 2A Due: Friday Mar 5 23:59</h3>
<h3>Part 2B Due: Friday Mar 12 23:59</h3>
<h3>Part 2C Due: Friday Mar 19 23:59</h3>
<h3>Part 2D Due: Friday Mar 26 23:59</h3>


<p>
  <b><a href="collab.html">Collaboration policy</a></b> //
  <b><a href="submit.html">Submit lab</a></b> //
  <b><a href="go.html">Setup Go</a></b> //
  <b><a href="guidance.html">Guidance</a></b> //
  <b><a href="https://piazza.com/mit/spring2021/6824">Piazza</a></b>
</p>

</div>


<hr>

<h3>Introduction</h3>

<p>
This is the first in a series of labs in which you'll build a
fault-tolerant key/value storage system. In this
lab you'll implement Raft, a replicated state machine protocol.
In the next lab you'll build a key/value service on top of
Raft. Then you will &ldquo;shard&rdquo; your service over
multiple replicated state machines for higher performance.

<p>
A replicated service achieves fault
tolerance by storing complete copies of its state (i.e., data)
on multiple replica servers.
Replication allows
the service to continue operating even if some of
its servers experience failures (crashes or a broken or flaky
network). The challenge is that failures may cause the
replicas to hold differing copies of the data.

<p>
Raft organizes client requests into a sequence, called
the log, and ensures that all the replica servers see the same log.
Each replica executes client requests
in log order, applying them to its local copy of the service's state.
Since all the live replicas
see the same log contents, they all execute the same requests
in the same order, and thus continue to have identical service
state. If a server fails but later recovers, Raft takes care of
bringing its log up to date. Raft will continue to operate as
long as at least a majority of the servers are alive and can
talk to each other. If there is no such majority, Raft will
make no progress, but will pick up where it left off as soon as
a majority can communicate again.

<p>
In this lab you'll implement Raft as a Go object type
with associated methods, meant to be used as a module in a
larger service. A set of Raft instances talk to each other with
RPC to maintain replicated logs. Your Raft interface will
support an indefinite sequence of numbered commands, also
called log entries. The entries are numbered with <em>index
numbers</em>. The log entry with a given index will eventually
be committed. At that point, your Raft should send the log
entry to the larger service for it to execute.

<p>
You should follow the design in the
<a href="../papers/raft-extended.pdf">extended Raft paper</a>,
with particular attention to Figure 2.
You'll implement most of what's in the paper, including saving
persistent state and reading it after a node fails and
then restarts. You will not implement cluster
membership changes (Section 6).

<p>
You may find this
<a href="https://thesquareplanet.com/blog/students-guide-to-raft/">guide</a>
useful, as well as this advice about
<a href="raft-locking.txt">locking</a>
and
<a href="raft-structure.txt">structure</a>
for concurrency.
For a
wider perspective, have a look at Paxos, Chubby, Paxos Made
Live, Spanner, Zookeeper, Harp, Viewstamped Replication, and
<a href="http://static.usenix.org/event/nsdi11/tech/full_papers/Bolosky.pdf">Bolosky et al.</a>
(Note: the student's guide was written several years ago, and part 2D in particular has
since changed. Make sure you understand why a particular implementation strategy makes
sense before blindly following it!)

<p>
We also provide a <a href="../notes/raft_diagram.pdf">diagram of Raft interactions</a> that can
help clarify how your Raft code interacts with the layers on top of it.

<p>
This lab is due in four parts. You must submit each part on the
corresponding due date.

<h3>Getting Started</h3>

<p>
If you have done Lab 1, you already have a copy of the lab
source code.
If not,
you can find directions for obtaining the source via git
in the <a href="lab-mr.html">Lab 1 instructions</a>.

<p>
We supply you with skeleton code <tt>src/raft/raft.go</tt>. We also
supply a set of tests, which you should use to drive your
implementation efforts, and which we'll use to grade your submitted
lab. The tests are in <tt>src/raft/test_test.go</tt>.

<p>
To get up and running, execute the following commands.
Don't forget the <tt>git pull</tt> to get the latest software.
<pre>
$ cd ~/6.824
$ git pull
...
$ cd src/raft
$ go test -race
Test (2A): initial election ...
--- FAIL: TestInitialElection2A (5.04s)
        config.go:326: expected one leader, got none
Test (2A): election after network failure ...
--- FAIL: TestReElection2A (5.03s)
        config.go:326: expected one leader, got none
...
$
</pre>

<h3>The code</h3>

Implement Raft by adding code to
<tt>raft/raft.go</tt>. In that file you'll find 
skeleton code, plus examples of how to send and receive
RPCs.

<p>
Your implementation must support the following interface, which
the tester and (eventually) your key/value server will use.
You'll find more details in comments in <tt>raft.go</tt>.

<pre>
// create a new Raft server instance:
rf := Make(peers, me, persister, applyCh)

// start agreement on a new log entry:
rf.Start(command interface{}) (index, term, isleader)

// ask a Raft for its current term, and whether it thinks it is leader
rf.GetState() (term, isLeader)

// each time a new entry is committed to the log, each Raft peer
// should send an ApplyMsg to the service (or tester).
type ApplyMsg</pre>

<p>
A service calls <tt>Make(peers,me,&hellip;)</tt> to create a
Raft peer. The peers argument is an array of network identifiers
of the Raft peers (including this one), for use with RPC. The
<tt>me</tt> argument is the index of this peer in the peers
array. <tt>Start(command)</tt> asks Raft to start the processing
to append the command to the replicated log. <tt>Start()</tt>
should return immediately, without waiting for the log appends
to complete. The service expects your implementation to send an
<tt>ApplyMsg</tt> for each newly committed log entry to the
<tt>applyCh</tt> channel argument to <tt>Make()</tt>.

<p>
<tt>raft.go</tt> contains example code that sends an RPC
(<tt>sendRequestVote()</tt>) and that handles an incoming RPC
(<tt>RequestVote()</tt>).
Your Raft peers should exchange RPCs using the labrpc Go
package (source in <tt>src/labrpc</tt>).
The tester can tell <tt>labrpc</tt> to delay RPCs,
re-order them, and discard them to simulate various network failures.
While you can temporarily modify <tt>labrpc</tt>, 
make sure your Raft works with the original <tt>labrpc</tt>,
since that's what we'll use to test and grade your lab.
Your Raft instances must interact only with RPC; for example,
they are not allowed to communicate using shared Go variables
or files.

<p>
Subsequent labs build on this lab, so it is important to give
yourself enough time to write solid code.

<h3>Part 2A: leader election <script>g("moderate")</script></h3>

<p class="todo">
Implement Raft leader election and heartbeats (<tt>AppendEntries</tt> RPCs with no
log entries). The goal for Part 2A is for a
single leader to be elected, for the leader to remain the leader
if there are no failures, and for a new leader to take over if the
old leader fails or if packets to/from the old leader are lost.
Run <tt>go test -run 2A -race</tt> to test your 2A code.

<ul class="hints">

<li>You can't easily run your Raft implementation directly; instead you should 
run it by way of the tester, i.e. <tt>go test -run 2A -race</tt>.

<li>Follow the paper's Figure 2. At this point you care about sending
and receiving RequestVote RPCs, the Rules for Servers that relate to
elections, and the State related to leader election,

<li>
Add the Figure 2 state for leader election
to the <tt>Raft</tt> struct in <tt>raft.go</tt>.
You'll also need to define a
struct to hold information about each log entry.

<li>
Fill in the <tt>RequestVoteArgs</tt> and
<tt>RequestVoteReply</tt> structs. Modify
<tt>Make()</tt> to create a background goroutine that will kick off leader
 election periodically by sending out <tt>RequestVote</tt> RPCs when it hasn't
 heard from another peer for a while.  This way a peer will learn who is the
 leader, if there is already a leader, or become the leader itself.  Implement
 the <tt>RequestVote()</tt> RPC handler so that servers will vote for one
 another.


<li>
To implement heartbeats, define an
<tt>AppendEntries</tt> RPC struct (though you may not
need all the arguments yet), and have the leader send
them out periodically. Write an
<tt>AppendEntries</tt> RPC handler method that resets
the election timeout so that other servers don't step
forward as leaders when one has already been elected.

<li>
Make sure the election timeouts in different peers don't always fire
at the same time, or else all peers will vote only for themselves and no
one will become the leader.

<li>
The tester requires that the leader send heartbeat RPCs no more than
ten times per second.

<li>
The tester requires your Raft to elect a new leader within five seconds of the
failure of the old leader (if a majority of peers can still
communicate). Remember, however, that leader election may require multiple
rounds in case of a split vote (which can happen if packets are lost or if
candidates unluckily choose the same random backoff times). You must pick
election timeouts (and thus heartbeat intervals) that are short enough that it's
very likely that an election will complete in less than five seconds even if it
requires multiple rounds.

<li>
The paper's Section 5.2 mentions election timeouts in the range of 150
to 300 milliseconds. Such a range only makes sense if the leader
sends heartbeats considerably more often than once per 150
milliseconds. Because the tester limits you to 10 heartbeats per
second, you will have to use an election timeout larger
than the paper's 150 to 300 milliseconds, but not too large, because then you
may fail to elect a leader within five seconds.

<li>
You may find Go's
<a href="https://golang.org/pkg/math/rand/">rand</a>
useful.

<li>
You'll need to write code that takes actions periodically or
after delays in time. The easiest way to do this is to create
a goroutine with a loop that calls
<a href="https://golang.org/pkg/time/#Sleep">time.Sleep()</a>;
(see the <tt>ticker()</tt> goroutine that <tt>Make()</tt>
creates for this purpose).
Don't use Go's <tt>time.Timer</tt> or <tt>time.Ticker</tt>, which
are difficult to use correctly.

<li>The <a href="guidance.html">Guidance page</a> has some 
  tips on how to develop and debug your code.

<li>
If your code has trouble passing the tests,
read the paper's Figure 2 again; the full logic for leader
election is spread over multiple parts of the figure.

<li>
Don't forget to implement <tt>GetState()</tt>.

<li>
The tester calls your Raft's <tt>rf.Kill()</tt> when it is
permanently shutting down an instance. You can check whether
<tt>Kill()</tt> has been called using <tt>rf.killed()</tt>.
You may want to do this in all loops, to avoid having
dead Raft instances print confusing messages.

  
<li>Go RPC sends only struct fields whose names start with capital letters.
  Sub-structures must also have capitalized field names (e.g. fields of log records
  in an array). The <tt>labgob</tt> package will warn you about this;
  don't ignore the warnings.

</ul>


<p>
Be sure you pass the 2A tests before submitting Part 2A, so that
you see something like this:

<pre>
$ go test -run 2A -race
Test (2A): initial election ...
  ... Passed --   4.0  3   32    9170    0
Test (2A): election after network failure ...
  ... Passed --   6.1  3   70   13895    0
PASS
ok      raft    10.187s
$
</pre>

<p>
Each "Passed" line contains five numbers; these are the time that the
test took in seconds, the number of Raft peers (usually 3 or 5), the
number of RPCs sent during the test, the total number of bytes in the
RPC messages, and the number of log entries
that Raft reports were committed. Your numbers will differ from those
shown here. You can ignore the numbers if you like, but they may help
you sanity-check the number of RPCs that your implementation sends.
For all of labs 2, 3, and 4, the grading script will fail your
solution if it takes more than 600 seconds for all of the tests
(<tt>go test</tt>), or if any individual test takes more than 120
seconds.

<h3>Part 2B: log <script>g("hard")</script></h3>

<p class="todo">
Implement the leader and follower code to append new log entries,
so that the <tt>go test -run 2B -race</tt> tests pass.

<ul class="hints">

<li>
Run <tt>git pull</tt> to get the latest lab software.

<li>
Your first goal should be to pass <tt>TestBasicAgree2B()</tt>.
Start by implementing <tt>Start()</tt>, then write the code
to send and receive new log entries via <tt>AppendEntries</tt> RPCs,
following Figure 2.

<li>
You will need to implement the election
restriction (section 5.4.1 in the paper).

<li>
One way to fail to reach agreement in the early Lab 2B
tests is to hold repeated elections even though the
leader is alive. Look for bugs in election timer
management, or not sending out heartbeats immediately after winning an
election.

<li>
Your code may have loops that repeatedly check for certain events.
Don't have these loops
execute continuously without pausing, since that
will slow your implementation enough that it fails tests.
Use Go's
<a href="https://golang.org/pkg/sync/#Cond">condition variables</a>,
or insert a
<tt>time.Sleep(10 * time.Millisecond)</tt> in each loop iteration.

<li>Do yourself a favor for future labs and write (or re-write) code
that's clean and clear.  For ideas, re-visit our
the <a href="guidance.html">Guidance page</a> with tips on how to
  develop and debug your code.

<li>If you fail a test, look over the code for the test
  in <tt>config.go</tt> and <tt>test_test.go</tt> to get a better
  understanding what the test is testing.  <tt>config.go</tt> also
  illustrates how the tester uses the Raft API.
  
</ul>

<p>
The tests for upcoming labs may fail your code if it runs too slowly.
You can check how much real time and CPU time your solution uses with
the time command. Here's typical output:

<pre>
$ time go test -run 2B
Test (2B): basic agreement ...
  ... Passed --   1.6  3   18    5158    3
Test (2B): RPC byte count ...
  ... Passed --   3.3  3   50  115122   11
Test (2B): agreement despite follower disconnection ...
  ... Passed --   6.3  3   64   17489    7
Test (2B): no agreement if too many followers disconnect ...
  ... Passed --   4.9  5  116   27838    3
Test (2B): concurrent Start()s ...
  ... Passed --   2.1  3   16    4648    6
Test (2B): rejoin of partitioned leader ...
  ... Passed --   8.1  3  111   26996    4
Test (2B): leader backs up quickly over incorrect follower logs ...
  ... Passed --  28.6  5 1342  953354  102
Test (2B): RPC counts aren't too high ...
  ... Passed --   3.4  3   30    9050   12
PASS
ok      raft    58.142s

real    0m58.475s
user    0m2.477s
sys     0m1.406s
$
</pre>

The "ok raft 58.142s" means that Go measured the time taken for the 2B
tests to be 58.142 seconds of real (wall-clock) time. The "user
0m2.477s" means that the code consumed 2.477 seconds of CPU time, or
time spent actually executing instructions (rather than waiting or
sleeping). If your solution uses much more than a minute of real time
for the 2B tests, or much more than 5 seconds of CPU time, you may run
into trouble later on. Look for time spent sleeping or waiting for RPC
timeouts, loops that run without sleeping or waiting for conditions or
channel messages, or large numbers of RPCs sent.

<h3>Part 2C: persistence <script>g("hard")</script></h3>

<p>
If a Raft-based server reboots it should resume service
where it left off. This requires
that Raft keep persistent state that survives a reboot. The
paper's Figure 2 mentions which state should be persistent.

<p>
A real implementation would write
Raft's persistent state to disk each time it changed, and would read the
state from
disk when restarting after a reboot. Your implementation won't use
the disk; instead, it will save and restore persistent state
from a <tt>Persister</tt> object (see <tt>persister.go</tt>).
Whoever calls <tt>Raft.Make()</tt> supplies a <tt>Persister</tt>
that initially holds Raft's most recently persisted state (if
any). Raft should initialize its state from that
<tt>Persister</tt>, and should use it to save its persistent
state each time the state changes. Use the <tt>Persister</tt>'s
<tt>ReadRaftState()</tt> and <tt>SaveRaftState()</tt> methods.

<p class="todo">
Complete the functions
<tt>persist()</tt>
and
<tt>readPersist()</tt> in <tt>raft.go</tt>
by adding code to save and restore persistent state. You will need to encode
(or "serialize") the state as an array of bytes in order to pass it to
the <tt>Persister</tt>. Use the <tt>labgob</tt> encoder;
see the comments in <tt>persist()</tt> and <tt>readPersist()</tt>.
<tt>labgob</tt> is like Go's <tt>gob</tt> encoder but
prints error messages if
you try to encode structures with lower-case field names.

<p class="todo">
Insert calls to <tt>persist()</tt> at the points where
your implementation changes persistent state.
Once you've done this,
you should pass the remaining tests.

<p class="note">
In order to avoid running out of memory, Raft must periodically
discard old log entries, but you <strong>do not</strong> have
to worry about this until the next lab.

<ul class="hints">

<li>
Run <tt>git pull</tt> to get the latest lab software.

<li>
Many of the 2C tests involve
servers failing and the network losing RPC requests or replies.
These events are non-deterministic, and you may get lucky and
pass the tests, even though your code has bugs.  Typically running
the test several times will expose those bugs.

<li>
You will probably need the optimization that backs up
nextIndex by more than one entry
at a time. Look at the <a href="../papers/raft-extended.pdf">extended Raft paper</a> starting at
the bottom of page 7 and top of page 8 (marked by a gray line).
The paper is vague about the details; you will need to fill in the gaps,
perhaps with the help of the 6.824 Raft lectures.

<li>
While 2C only requires you to implement persistence and fast 
log backtracking, 2C test failures might be related to previous parts of 
your implementation. Even if you pass 2A and 2B tests consistently, you 
may still have election or log bugs that are exposed on 2C tests.
</ul>

<p>
Your code should pass all the 2C tests (as shown below), as well as
the 2A and 2B tests.

<pre>
$ go test -run 2C -race
Test (2C): basic persistence ...
  ... Passed --   7.2  3  206   42208    6
Test (2C): more persistence ...
  ... Passed --  23.2  5 1194  198270   16
Test (2C): partitioned leader and one follower crash, leader restarts ...
  ... Passed --   3.2  3   46   10638    4
Test (2C): Figure 8 ...
  ... Passed --  35.1  5 9395 1939183   25
Test (2C): unreliable agreement ...
  ... Passed --   4.2  5  244   85259  246
Test (2C): Figure 8 (unreliable) ...
  ... Passed --  36.3  5 1948 4175577  216
Test (2C): churn ...
  ... Passed --  16.6  5 4402 2220926 1766
Test (2C): unreliable churn ...
  ... Passed --  16.5  5  781  539084  221
PASS
ok      raft    142.357s
$ 
</pre>

<p>It is a good idea to run the tests multiple times before
  submitting and check that each run prints <tt>PASS</tt>.
<pre>
$ for i in {0..10}; do go test; done
</pre>


<h3>Part 2D: log compaction <script>g("hard")</script></h3>

<p>
As things stand now with your code, a rebooting service replays the
complete Raft log in order to restore its state. However, it's not
practical for a long-running service to remember the complete Raft log
forever. Instead, you'll modify Raft to cooperate to save
space: from time to time a service will persistently store a "snapshot"
of its current state, and Raft will discard log entries that precede
the snapshot. When a service falls far behind the leader
and must catch up, the service first installs a snapshot and then
replays log entries from after the point at which the snapshot
was created.
Section 7 of the
<a href="../papers/raft-extended.pdf">extended Raft paper</a>
outlines the scheme; you will have to design the details.

<p>
You may find it helpful to refer to the <a href="../notes/raft_diagram.pdf">diagram of Raft
    interactions</a> to understand how the replicated service and Raft communicate.

<p>To support snapshots, we need an interface between the service and
  the Raft library.  The Raft paper doesn't specify this interface,
  and several designs are possible.  To allow for a simple
  implementation, we decided on the following interface between
  service and Raft:
<li><tt>Snapshot(index int, snapshot []byte)</tt>
<li><tt>CondInstallSnapshot(lastIncludedTerm int, lastIncludedIndex int, snapshot []byte) bool</tt>
</ul>

<p>A service calls <tt>Snapshot()</tt> to communicate the snapshot of its state to Raft. The
snapshot includes all info up to and including index. This means the corresponding Raft peer no
longer needs the log through (and including) index. Your Raft implementation should trim its log as
much as possible. You must revise your Raft code to operate while storing only the tail of the log. 

<p>
As discussed in the extended Raft paper, Raft leaders must sometimes tell lagging Raft peers to
update their state by installing a snapshot. 
You need to implement <tt>InstallSnapshot</tt> RPC senders and handlers for installing snapshots when this situation arises.
This is in contrast to <tt>AppendEntries</tt>, which
sends log entries that are then applied one by one by the service. 

<p>
Note that <tt>InstallSnapshot</tt> RPCs are sent <i>between</i> Raft peers, whereas the provided
skeleton functions <tt>Snapshot/CondInstallSnapshot</tt> are used by the service to communicate to Raft.

<p>When a follower receives and handles an InstallSnapshot RPC, it must hand the included snapshot
to the service using Raft.  The InstallSnapshot handler can use the <tt>applyCh</tt> to send the
snapshot to the service, by putting the snapshot in <tt>ApplyMsg</tt>. The service reads from
<tt>applyCh</tt>, and invokes <tt>CondInstallSnapshot</tt> with the snapshot to tell Raft that the service is switching to
the passed-in snapshot state, and that Raft should update its log at the same time.
(See <tt>applierSnap()</tt> in <tt>config.go</tt> to see how the tester service
does this)

<p><tt>CondInstallSnapshot</tt> should refuse to install a snapshot if it is an old snapshot (i.e.,
if Raft has processed entries after the snapshot's <tt>lastIncludedTerm/lastIncludedIndex</tt>).
This is because Raft may handle other RPCs and send messages on the <tt>applyCh</tt> after it
handled the <tt>InstallSnapshot</tt> RPC, and before <tt>CondInstallSnapshot</tt> was invoked by the
service. It is not OK for Raft to go back to an older snapshot, so older snapshots must be refused.
When your implementation refuses the snapshot, <tt>CondInstallSnapshot</tt> should just return
<tt>false</tt> so that the service knows it shouldn't switch to the snapshot.

<p>If the snapshot is recent, then Raft should trim its log, persist
the new state, return <tt>true</tt>, and the service should switch
to the snapshot before processing the next message on
the <tt>applyCh</tt>.

<p><tt>CondInstallSnapshot</tt> is one way of updating the Raft and
service state; other interfaces between service and raft are possible
too.  This particular design allows your implementation to do the
check whether an snapshot must be installed or not in one place and
atomically switch both the service and Raft to the snapshot.  You are
free to implement Raft in a way that <tt>CondInstallSnapShot</tt> can
always return <tt>true</tt>; if your implementation passes the tests,
you receive full credit.

<p class="todo">
Modify your Raft code to support snapshots: implement Snapshot,
CondInstallSnapshot, and the InstallSnapshot RPC, as well as the
changes to Raft to support these (e.g, continue to operate with a
trimmed log).  Your solution is complete when it passes the 2D tests
and all the Lab 2 tests.  (Note that lab 3 will test snapshots more
thoroughly than lab 2 because lab 3 has a real service to stress
Raft's snapshots.)
</p> 

<ul class="hints">

<li>Send the entire snapshot in a single InstallSnapshot RPC.
Don't implement Figure 13's <tt>offset</tt> mechanism for
splitting up the snapshot.

<li> Raft must discard old log entries in a way that allows the Go garbage collector to free and re-use the
memory; this requires that there be no reachable references (pointers)
to the discarded log entries.

<li> Raft logs can no longer use the position of a log entry or the length of the log to determine log
    entry indices; you will need to use an indexing scheme independent of log position.

    <li> Even when the log is trimmed, your implemention still needs to properly send the term and index
    of the entry prior to new entries in <tt>AppendEntries</tt> RPCs; this may require saving and referencing
    the latest snapshot's <tt>lastIncludedTerm/lastIncludedIndex</tt> (consider whether this
    should be persisted). 

<li>Raft must store each snapshot in the persister object using
<tt>SaveStateAndSnapshot()</tt>.


<!-- <li><tt>Snapshot()</tt> <i>cannot</i> always set the tail of the log -->
<!--   to the index provided by the caller. -->

<li>
A reasonable amount of time to consume for the full set of
Lab 2 tests (2A+2B+2C+2D) is 8 minutes of real time and one and a
half minutes of CPU time.

</ul>

</body>
</html>
<!--  LocalWords:  transactional RPC snapshotting Paxos Viewstamped -->
<!--  LocalWords:  Bolosky et al else's github src labrpc cd ok RPCs -->
<!--  LocalWords:  TestInitialElection TestReElection rf persister -->
<!--  LocalWords:  applyCh isleader GetState isLeader rpc -->
<!--  LocalWords:  ApplyMsg Persister's SaveRaftState ReadRaftState -->
<!--  LocalWords:  readPersist sendRequestVote RequestVote struct -->
<!--  LocalWords:  RequestVoteArgs RequestVoteReply structs goroutine -->
<!--  LocalWords:  AppendEntries AppendEntry TestBasicAgree -->
<!--  LocalWords:  InstallSnapshot -->
